package main

import "fmt"

//#link: https://leetcode-cn.com/problems/longest-common-subsequence/
func main() {
	text1 := "abcde"
	text2 := "ace"
	fmt.Println(longestCommonSubsequence(text1, text2))
}

//思路:参考了官方题解,dp[i][j]数组表示取text1的前i个和text2的前j个数，当text1[i]==text2[j]时，dp[i][j]=dp[i-1][j-1],
//若不相等，则取拿到i和拿到j的最大值，即dp[i][j]=max(dp[i][j-1],dp[i-1][j])
func longestCommonSubsequence(text1 string, text2 string) int {
	dp := make([][]int, len(text1)+1)
	for i := range dp {
		dp[i] = make([]int, len(text2)+1)
	}
	for i, value := range []byte(text1) {
		for j := 0; j < len(text2); j++ {
			if value == text2[j] {
				dp[i+1][j+1] = dp[i][j] + 1

			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}
		}
	}
	return dp[len(text1)][len(text2)]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
